package com.cdream.basic.algorithm.leetcode.dfs;

import java.util.*;
import java.util.stream.Collectors;

public class Question1239 {
    public static void main(String[] args) {
        int n = 10, m = 1 << n;
        int[] cnt = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 26; j++) {
                if (((i>>j) & 1)==1) cnt[i]++;
            }
        }
        System.out.println(Arrays.toString(cnt));
    }

    private Set<Character> used = new HashSet<>();
    private int max = 0;

    public int maxLength(List<String> arr) {
        arr = arr.stream().filter(this::isNotDuplicate).collect(Collectors.toList());
        dfs(arr, 0);
        return max;
    }

    private boolean isNotDuplicate(String a) {
        HashSet<Character> cSet = new HashSet<>();
        for (char c : a.toCharArray()) {
            cSet.add(c);
        }
        return cSet.size() == a.length();
    }

    private void dfs(List<String> arr, int i) {
        if (i == arr.size()) {
            max = Math.max(max, used.size());
            return;
        }
        dfs(arr, i + 1);
        String element = arr.get(i);
        char[] eles = element.toCharArray();

        for (char ele : eles) {
            if (used.contains(ele)) {
                return;
            }
        }
        for (char ele : eles) {
            used.add(ele);
        }
        dfs(arr, i + 1);
        for (char ele : eles) {
            used.remove(ele);
        }
    }
}
